/*
 * Transmissão de Dados - Trabalho 4
 *
 * Alex Oliveira   - 06/30403
 * Danilo Trindade - 06/82039
 */

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <time.h>
#include <math.h>
#include "grafo.h"

static void plota_pontos(matriz_t m, int raio);
static inline int calc_custo(matriz_t m, int a, int b);
void extrai_pontos(matriz_t m, grafo_t g, int raio);

static inline int mais_ou_menos(int x);
static inline int delta_x(matriz_t m, int a, int b);
static inline int delta_y(matriz_t m, int a, int b);

void garante_conectividade(matriz_t m, grafo_t g, int n);


/*
 * Cria uma nova matriz com os valores recebidos, aloca o espaço, preenche os
 * nós e preenche a matriz.
 * Lembrar que onde não há nó na matriz, deve haver -1.
 */
matriz_t new_matriz(int altura, int largura, int nos, int raio) {

	/* Inicializa as variáveis. */
	matriz_t m;
	m.altura = altura;
	m.largura = largura;
	m.quant_nos = nos;

	/* Aloca a memória. */
	m.no = malloc(nos * sizeof(no_t));
	m.celula = malloc(altura * sizeof(int *));
	for (int i = 0; i < altura; ++i) {
		m.celula[i] = malloc(largura * sizeof(int));

		/* Coloca -1 em todas células para indicar que não há nó nelas. */
		for (int j = 0; j < largura; ++j) {
			m.celula[i][j] = -1;
		}
	}

	plota_pontos(m, raio);

	return m;
}


/*
 * Libera o espaço da memória que a matriz alocou e zera as variáveis.
 */
void del_matriz(matriz_t m) {

	/* Libera a memória. */
	for (int i = 0; i < m.altura; i++) {
		free(m.celula[i]);
	}
	free(m.celula);
	free(m.no);

	/* Zera as variáveis. */
	m.celula = NULL;
	m.no = NULL;
	m.altura = m.largura = m.quant_nos = 0;
}


/*
 * Cria um novo grafo, aloca espaço para suas variáveis e usa os pontos da
 * matriz para montar esse grafo.
 * OBS: Essa função modifica a matriz.
 */
grafo_t new_grafo(matriz_t m, int raio) {
	grafo_t g;
	bool ja_tem1, ja_tem2;

	/* Alocação e inicialização de primeiro nível. */
	g.custo = malloc(m.quant_nos * sizeof(int *));
	g.caminho = malloc(m.quant_nos * sizeof(int *));
	g.atualizou = malloc(m.quant_nos * sizeof(bool));
	g.vizinho = malloc(m.quant_nos * sizeof(int *));
	g.quant_vizinhos = calloc(m.quant_nos, sizeof(int));
	g.quant_vertices = m.quant_nos;

	/* Alocação e inicialização de segundo nível. */
	for (int i = 0; i < m.quant_nos; ++i) {
		g.custo[i] = malloc(m.quant_nos * sizeof(int));
		g.caminho[i] = malloc(m.quant_nos * sizeof(int));
		g.atualizou[i] = true;
		g.vizinho[i] = malloc(MAXVIZINHOS * sizeof(int));

		/* Alocação e inicialização de terceiro nível. */
		for (int j = 0; j < m.quant_nos; ++j) {
			g.custo[i][j] = INF;
			g.caminho[i][j] = -1;
		}
	}

	extrai_pontos(m, g, raio);

	for (int i = 0; i < g.quant_vertices; i++){
		g.custo[i][i] = 0;
		g.caminho[i][i] = i;

		ja_tem1 = false;
		ja_tem2 = false;
		for (int k = 0; k < g.quant_vizinhos[i]; k++){
			if (g.vizinho[i][k] == i-1){
				ja_tem1 = true;
			}
			if (g.vizinho[i][k] == i+1){
				ja_tem2 = true;
			}
		}

		if ((i > 0) && (i < g.quant_vertices-1)){
			if (!(ja_tem1)){
				g.vizinho[i][g.quant_vizinhos[i]] = i-1;
				g.quant_vizinhos[i]++;
			}
			if (!(ja_tem2)){
				g.vizinho[i][g.quant_vizinhos[i]] = i+1;
				g.quant_vizinhos[i]++;
			}

		} else {
			if (i == 0){
				if (!(ja_tem2)){
					g.vizinho[i][g.quant_vizinhos[i]] = i+1;
					g.quant_vizinhos[i]++;
				}
			} else {
				if (!(ja_tem1)){
					g.vizinho[i][g.quant_vizinhos[i]] = i-1;
					g.quant_vizinhos[i]++;
				}
			}
		}
	}

	return g;
}


/*
 * Libera a memória e zera todas as variáveis de um grafo.
 */
void del_grafo(grafo_t g) {

	/* Libera a memória. */
	for (int i = 0; i < g.quant_vertices; ++i) {
		free(g.custo[i]);
		free(g.caminho[i]);
		free(g.vizinho[i]);
	}
	free(g.custo);
	free(g.caminho);
	free(g.atualizou);
	free(g.vizinho);
	free(g.quant_vizinhos);

	/* Zera as variáveis. */
	g.custo = NULL;
	g.caminho = NULL;
	g.atualizou = NULL;
	g.vizinho = NULL;
	g.quant_vizinhos = NULL;
	g.quant_vertices = 0;
}


/*
 * Plota todos os pontos na matriz, de acordo com o raio recebido.
 * Não esquecer que deixar as bordas livres, todos os pontos a, no mínimo, um
 * raio de distância do fim da matriz.
 */
void plota_pontos(matriz_t m, int r) {
	no_t old, new;

	srand(time(NULL));

	/* Gera o ponto de partida, que não vai pra matriz. */
	old.x = rand() % (m.largura - 2 * r) + r;
	old.y = rand() % (m.altura - 2 * r) + r;

	/* Gera e plota todos os pontos dentro do raio do anterior. */
	for (int i = 0; i < m.quant_nos; old = new, i++) {
		do {
			do {
				new.x = old.x + mais_ou_menos(rand() % r);
			} while (new.x < r || new.x >= m.largura -r);
			do {
				new.y = old.y + mais_ou_menos(rand() % r);
			} while (new.y < r || new.y >= m.altura -r);
		} while (m.celula[new.y][new.x] >= 0);  /* garante que não vai cair em cima de outro ponto*/
		m.no[i] = new;
		m.celula[new.y][new.x] = i;
	}
}


/*
 * Calcula a distância quadrada entre dois pontos da matriz.
 */
int calc_custo(matriz_t m, int a, int b) {
	return pow(delta_x(m, a, b), 2) + pow(delta_y(m, a, b), 2);
}


/*
 * Percorre os nós da matriz, procurando os vizinhos de cada um e montando o
 * array de adjacências.
 * OBS: Essa função modifica a matriz.
 */
void extrai_pontos(matriz_t m, grafo_t g, int raio) {

    /* Percorre todos os nós, procurando seus vizinhos. */
	int no = 0;
	bool ja_tem = false;

    while (no < m.quant_nos) {
    	int x_no = m.no[no].x;
    	int y_no = m.no[no].y;
		for (int y = y_no - raio; y <= y_no + raio; ++y) {
			for (int x = x_no - raio; x <= x_no + raio; ++x) {
				int vizinho = m.celula[y][x];
				if (vizinho >= 0 && vizinho != no) {
					ja_tem = false;
					for (int i = 0; i < g.quant_vizinhos[no]; i++){
						if (g.vizinho[no][i] == vizinho){
							ja_tem = true;
						}
					}
					if (!(ja_tem)){
						int x_vizinho = m.no[vizinho].x;
						int y_vizinho = m.no[vizinho].y;

						/* Acrescenta esse vizinho na lista de vizinhos do nó atual
						e vice-versa. */
						g.vizinho[no][g.quant_vizinhos[no]] = vizinho;
						g.vizinho[vizinho][g.quant_vizinhos[vizinho]] = no;
						g.quant_vizinhos[no] += 1;
						g.quant_vizinhos[vizinho] += 1;

						/* Calcula o custo do nó atual até esse vizinho. */
						g.custo[no][vizinho] = g.custo[vizinho][no] = calc_custo(m, no, vizinho);
						g.caminho[no][vizinho] = vizinho;
						g.caminho[vizinho][no] = no;

						/* Se algum dos dois nós não aguentar mais
						vizinhos, retira ele da matriz pra ninguém mais tentar
						adicionar ele como vizinho. */
						if (g.quant_vizinhos[vizinho] == MAXVIZINHOS) {
							m.celula[y_vizinho][x_vizinho] = -1;
						}
						if (g.quant_vizinhos[no] == MAXVIZINHOS) {
							m.celula[y_no][x_no] = -1;
							goto inc_l;  /* vai direto pro próximo nó*/
						}
					}

				}
			}
		}

		inc_l:  /* incrementa para o próximo nó*/
		no++;
	}

    /* Garante que não há ilhas. Se um nó tiver com o máximo de vizinhos, o
    anterior deve estar entre os vizinhos. */
    for (int n = 0; n < g.quant_vertices; ++n) {
    	garante_conectividade(m, g, n);
	}
}


/*
 * Garante que um nó estará conectado com todos os outros.
 */
void garante_conectividade(matriz_t m, grafo_t g, int n) {

	if (g.quant_vizinhos[n] == MAXVIZINHOS) {

		/* Percorre todos os vizinhos procurando o anterior. */
		bool tem_anterior = false;
		for (int i = 0; i < MAXVIZINHOS; ++i) {
			if (g.vizinho[n][i] == n - 1) {
				tem_anterior = true;
				break;
			}
		}

		/* Acrescenta esse vizinho na lista de vizinhos do nó atual
		 e vice-versa. */
		if (g.quant_vizinhos[n-1] == MAXVIZINHOS) {
			g.quant_vizinhos[n-1]--;
		}
		g.vizinho[n][MAXVIZINHOS - 1] = n - 1;
		g.vizinho[n - 1][g.quant_vizinhos[n - 1]] = n;
		g.quant_vizinhos[n] += 1;
		g.quant_vizinhos[n - 1] += 1;

		/* Calcula o custo do nó atual até esse vizinho. */
		g.custo[n][n - 1] = g.custo[n - 1][n] = calc_custo(m, n, n - 1);
		g.caminho[n][n - 1] = n - 1;
		g.caminho[n - 1][n] = n;

	}
}


/*
 * Retorna x ou -x, aleatoriamente.
 */
int mais_ou_menos(int x) {
	return (rand() % 2) ? x : -x;
}


/*
 * Calcula a diferença da coordenada x de dois pontos da matriz.
 */
int delta_x(matriz_t m, int a, int b) {
	return abs(m.no[a].x - m.no[b].x);
}


/*
 * Calcula a diferença da coordenada y de dois pontos da matriz.
 */
int delta_y(matriz_t m, int a, int b) {
	return abs(m.no[a].y - m.no[b].y);
}
